1. Field of the Invention
This invention relates to microprocessor caches and, more particularly, to cache data replacement mechanisms.
2. Description of the Related Art
Since a computer system's main memory is typically designed for density rather than speed, microprocessor designers have added caches to their designs to reduce the microprocessor's need to directly access main memory. A cache is a small memory that is more quickly accessible than the main memory. Caches are typically constructed of fast memory cells such as static random access memories (SRAMs) which have faster access times and bandwidth than the memories used for the main system memory (typically dynamic random access memories (DRAMs) or synchronous dynamic random access memories (SDRAMs)).
Modern microprocessors typically include on-chip cache memory. In many cases, microprocessors include an on-chip hierarchical cache structure that may include a level one (L1), a level two (L2) and in some cases a level three (L3) cache memory. Typical cache hierarchies may employ a small, fast L1 cache that may be used to store the most frequently used cache lines. The L2 cache may be a larger and possibly slower cache for storing cache lines that are accessed frequently but don't fit in the L1. The L3 cache may be still larger than the L2 cache and may be used to store cache lines that are accessed frequently but do not fit in the L2 cache. Having a cache hierarchy as described above may improve processor performance by reducing the latencies associated with memory access by the processor core.
In a typical cache design, any given block of data may be placed only in one of some small number of physical locations, called a set (commonly referred to as a set associative cache). The maximum number of blocks per set is the associativity of the cache. Once a given set is full, each time new data must be brought into that set, an existing entry must be overwritten or replaced by the new data. Some type of algorithm must be used to determine which existing entry will be overwritten during a replacement. One type of replacement algorithm is the least recently used (LRU) algorithm. In the LRU algorithm, the time order of all the entries in each set is tracked, and as the name implies, the least recently used entry is replaced. This algorithm works well if the associativity is small. For higher associativity, keeping track of the LRU position becomes complex and requires significant amounts of storage for the ordering information.